home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / b / b.lha / B / src / bed / node.c < prev    next >
Encoding:
C/C++ Source or Header  |  1988-11-24  |  10.1 KB  |  654 lines
  1. /* Copyright (c) Stichting Mathematisch Centrum, Amsterdam, 1984. */
  2. static char rcsid[] = "$Header: node.c,v 2.4 85/08/22 16:05:27 timo Exp $";
  3.  
  4. /*
  5.  * B editor -- Parse tree and Focus stack.
  6.  */
  7.  
  8. #include "b.h"
  9. #include "bobj.h"
  10.  
  11. #include "node.h"
  12.  
  13. #define Register register
  14.     /* Used for registers 4-6.  Define as empty macro on PDP */
  15.  
  16.  
  17. /*
  18.  * Lowest level routines for 'node' data type.
  19.  */
  20.  
  21. #define Isnode(n) ((n) && (n)->type == Nod)
  22.  
  23. #define Nchildren(n) ((n)->len)
  24. #define Symbol(n) ((n)->n_symbol)
  25. #define Child(n, i) ((n)->n_child[(i)-1])
  26. #define Marks(n) ((n)->n_marks)
  27. #define Width(n) ((n)->n_width)
  28.  
  29.  
  30. /*
  31.  * Routines which are macros for the compiler but real functions for lint,
  32.  * so it will check the argument types more strictly.
  33.  */
  34.  
  35. #ifdef lint
  36. node
  37. nodecopy(n)
  38.     node n;
  39. {
  40.     return (node) copy((value) n);
  41. }
  42.  
  43. noderelease(n)
  44.     node n;
  45. {
  46.     release((value)n);
  47. }
  48.  
  49. nodeuniql(pn)
  50.     node *pn;
  51. {
  52.     uniql((value*)pn);
  53. }
  54. #endif lint
  55.  
  56.  
  57. /*
  58.  * Allocate a new node.
  59.  */
  60.  
  61. Visible node
  62. newnode(nch, sym, children)
  63.     register int nch;
  64.     Register int sym;
  65.     register node children[];
  66. {
  67.     register node n = (node) grab_node(nch); /* Must preset with zeros! */
  68.  
  69.     Symbol(n) = sym;
  70.     for (; nch > 0; --nch)
  71.         Child(n, nch) = children[nch-1];
  72.     Width(n) = evalwidth(n);
  73.     return n;
  74. }
  75.  
  76.  
  77. /*
  78.  * Macros to change the fields of a node.
  79.  */
  80.  
  81. #define Locchild(pn, i) \
  82.     (Refcnt(*(pn)) == 1 || nodeuniql(pn), &Child(*(pn), i))
  83. #define Setmarks(pn, x) \
  84.     (Refcnt(*(pn)) == 1 || nodeuniql(pn), Marks(*(pn))=(x))
  85. #define Setwidth(pn, w) (Refcnt(*(pn)) == 1 || nodeuniql(pn), Width(*(pn))=w)
  86.  
  87.  
  88. /*
  89.  * Change a child of a node.
  90.  * Like replace(), it does not increase the reference count of n.
  91.  */
  92.  
  93. Visible Procedure
  94. setchild(pn, i, n)
  95.     register node *pn;
  96.     register int i;
  97.     Register node n;
  98. {
  99.     register node *pch;
  100.     register node oldchild;
  101.  
  102.     Assert(Isnode(*pn));
  103.     pch = Locchild(pn, i);
  104.     oldchild = *pch;
  105.     *pch = n;
  106.     repwidth(pn, oldchild, n);
  107.     noderelease(oldchild);
  108. }
  109.  
  110.  
  111. /*
  112.  * Lowest level routines for 'path' data type.
  113.  */
  114.  
  115. #define NPATHFIELDS 6
  116.  
  117. #define Parent(p) ((p)->p_parent)
  118. #define Tree(p) ((p)->p_tree)
  119. #define Ichild(p) ((p)->p_ichild)
  120. #define Ycoord(p) ((p)->p_ycoord)
  121. #define Xcoord(p) ((p)->p_xcoord)
  122. #define Level(p) ((p)->p_level)
  123.  
  124.  
  125. /*
  126.  * Routines which are macros for the compiler but real functions for lint,
  127.  * so it will check the argument types more strictly.
  128.  */
  129.  
  130. #ifdef lint
  131. Visible path
  132. pathcopy(p)
  133.     path p;
  134. {
  135.     return (path) copy((value) p);
  136. }
  137.  
  138. Visible Procedure
  139. pathrelease(p)
  140.     path p;
  141. {
  142.     release((value)p);
  143. }
  144.  
  145. Visible Procedure
  146. pathuniql(pp)
  147.     path *pp;
  148. {
  149.     uniql((value*)pp);
  150. }
  151. #endif lint
  152.  
  153.  
  154. /*
  155.  * Allocate a new path entry.
  156.  */
  157.  
  158. Visible path
  159. newpath(pa, n, i)
  160.     register path pa;
  161.     register node n;
  162.     Register int i;
  163. {
  164.     register path p = (path) grab_path();
  165.  
  166.     Parent(p) = pa;
  167.     Tree(p) = n;
  168.     Ichild(p) = i;
  169.     Ycoord(p) = Xcoord(p) = Level(p) = 0;
  170.     return p;
  171. }
  172.  
  173.  
  174. /*
  175.  * Macros to change the fields of a path entry.
  176.  */
  177.  
  178. #define Uniqp(pp) (Refcnt(*(pp)) == 1 || pathuniql(pp))
  179.  
  180. #define Setcoord(pp, y, x, level) (Uniqp(pp), \
  181.     (*(pp))->p_ycoord = y, (*(pp))->p_xcoord = x, (*(pp))->p_level = level)
  182.  
  183. #define Locparent(pp) (Uniqp(pp), &Parent(*(pp)))
  184.  
  185. #define Loctree(pp) (Uniqp(pp), &Tree(*(pp)))
  186.  
  187. #define Addmarks(pp, x) (Uniqp(pp), \
  188.     (*(pp))->p_addmarks |= (x), (*(pp))->p_delmarks &= ~(x))
  189.  
  190. #define Delmarks(pp, x) (Uniqp(pp), \
  191.     (*(pp))->p_delmarks |= (x), (*(pp))->p_addmarks &= ~(x))
  192.  
  193.  
  194. Hidden Procedure
  195. connect(pp)
  196.     path *pp;
  197. {
  198.     register path p = *pp;
  199.     register path pa = Parent(p);
  200.     register path *ppa;
  201.     register node n;
  202.     register node npa;
  203.     register node *pn;
  204.     node oldchild;
  205.     node *pnpa;
  206.     int i;
  207.     markbits add;
  208.     markbits del;
  209.  
  210.     if (!pa)
  211.         return;
  212.     i = ichild(p);
  213.     n = Tree(p);
  214.     if (Child(Tree(pa), i) == n)
  215.         return; /* Still connected */
  216.  
  217.     n = nodecopy(n);
  218.     ppa = Locparent(pp);
  219.     pnpa = Loctree(ppa);
  220.     pn = Locchild(pnpa, i);
  221.     oldchild = *pn;
  222.     *pn = n;
  223.     repwidth(pnpa, oldchild, n);
  224.     noderelease(oldchild);
  225.  
  226.     add = p->p_addmarks;
  227.     del = p->p_delmarks;
  228.     if (add|del) {
  229.         p = *pp;
  230.         p->p_addmarks = 0;
  231.         p->p_delmarks = 0;
  232.         if (add)
  233.             Addmarks(ppa, add);
  234.         npa = *pnpa;
  235.         if (del) {
  236.             for (i = Nchildren(npa); i > 0; --i)
  237.                 if (i != ichild(p))
  238.                     del &= ~marks(Child(npa, i));
  239.             Delmarks(ppa, del);
  240.         }
  241.         Setmarks(pnpa, Marks(npa)&~del|add);
  242.     }
  243. }
  244.  
  245.  
  246. /*
  247.  * The following procedure sets the new width of node *pn when child
  248.  * oldchild is replaced by child newchild.
  249.  * This was added because the original call to evalwidth seemed to
  250.  * be the major caller of noderepr() and fwidth().
  251.  */
  252.  
  253. Hidden Procedure
  254. repwidth(pn, old, new)
  255.     register node *pn;
  256.     Register node old;
  257.     Register node new;
  258. {
  259.     register int w = Width(*pn);
  260.     register int oldwidth = width(old);
  261.     register int newwidth = width(new);
  262.  
  263.     if (w < 0) {
  264.         if (oldwidth > 0)
  265.             oldwidth = 0;
  266.         if (newwidth > 0)
  267.             newwidth = 0;
  268.     }
  269.     else {
  270.         Assert(oldwidth >= 0);
  271.         if (newwidth < 0) {
  272.             Setwidth(pn, newwidth);
  273.             return;
  274.         }
  275.     }
  276.     newwidth -= oldwidth;
  277.     if (newwidth)
  278.         Setwidth(pn, w + newwidth);
  279. }
  280.  
  281.  
  282. Visible Procedure
  283. markpath(pp, new)
  284.     register path *pp;
  285.     register markbits new;
  286. {
  287.     register node *pn;
  288.     register markbits old;
  289.  
  290.     Assert(Type(Tree(*pp)) == Nod);
  291.     old = Marks(Tree(*pp));
  292.     if ((old|new) == old)
  293.         return; /* Bits already set */
  294.  
  295.     pn = Loctree(pp);
  296.     Setmarks(pn, old|new);
  297.     Addmarks(pp, new&~old);
  298. }
  299.  
  300.  
  301. Visible Procedure
  302. unmkpath(pp, del)
  303.     register path *pp;
  304.     register int del;
  305. {
  306.     register node *pn;
  307.     register markbits old;
  308.  
  309.     Assert(Type(Tree(*pp)) == Nod);
  310.     old = Marks(Tree(*pp));
  311.     if ((old&~del) == del)
  312.         return;
  313.  
  314.     pn = Loctree(pp);
  315.     Setmarks(pn, old&~del);
  316.     Delmarks(pp, del&old);
  317. }
  318.  
  319.  
  320. Hidden Procedure
  321. clearmarks(pn)
  322.     register node *pn;
  323. {
  324.     register int i;
  325.  
  326.     if (!Marks(*pn))
  327.         return;
  328.     if (Isnode(*pn)) {
  329.         Setmarks(pn, 0);
  330.         for (i = Nchildren(*pn); i > 0; --i)
  331.             clearmarks(Locchild(pn, i));
  332.     }
  333. }
  334.  
  335.  
  336. /*
  337.  * Replace the focus' tree by a new node.
  338.  * WARNING: n's reference count is not increased!
  339.  * You can also think of this as: replace(pp, n) implies noderelease(n).
  340.  * Mark bits are copied from the node being replaced.
  341.  */
  342.  
  343. Visible Procedure
  344. replace(pp, n)
  345.     register path *pp;
  346.     register node n;
  347. {
  348.     register node *pn;
  349.     register markbits old;
  350.  
  351.     pn = Loctree(pp);
  352.     if (Type(*pn) == Nod)
  353.         old = Marks(*pn);
  354.     else
  355.         old = 0;
  356.     noderelease(*pn);
  357.     *pn = n;
  358.     if (Type(n) == Nod) {
  359.         clearmarks(pn);
  360.         if (old)
  361.             Setmarks(pn, old);
  362.     }
  363.     else if (old)
  364.         Addmarks(pp, old);
  365. }
  366.  
  367.  
  368. Visible bool
  369. up(pp)
  370.     register path *pp;
  371. {
  372.     register path p = *pp;
  373.  
  374.     if (!Parent(p))
  375.         return No;
  376.  
  377.     connect(pp);
  378.     p = pathcopy(Parent(*pp));
  379.     pathrelease(*pp);
  380.     *pp = p;
  381.     return Yes;
  382. }
  383.  
  384.  
  385. Visible bool
  386. downi(pp, i)
  387.     register path *pp;
  388.     register int i;
  389. {
  390.     register node n;
  391.     auto int y;
  392.     auto int x;
  393.     auto int level;
  394.  
  395.     n = Tree(*pp);
  396.     if (!Isnode(n) || i < 1 || i > Nchildren(n))
  397.         return No;
  398.  
  399.     y = Ycoord(*pp);
  400.     x = Xcoord(*pp);
  401.     level = Level(*pp);
  402.     *pp = newpath(*pp, nodecopy(Child(n, i)), i);
  403.     evalcoord(n, i, &y, &x, &level);
  404.     Setcoord(pp, y, x, level);
  405.     return Yes;
  406. }
  407.  
  408.  
  409. Visible bool
  410. downrite(pp)
  411.     register path *pp;
  412. {
  413.     if (!Isnode(Tree(*pp)))
  414.         return No;
  415.     return downi(pp, Nchildren(Tree(*pp)));
  416. }
  417.  
  418.  
  419. Visible bool
  420. left(pp)
  421.     register path *pp;
  422. {
  423.     register int i;
  424.  
  425.     i = ichild(*pp) - 1;
  426.     if (i <= 0)
  427.         return No;
  428.     if (!up(pp))
  429.         return No;
  430.     return downi(pp, i);
  431. }
  432.  
  433.  
  434. Visible bool
  435. rite(pp)
  436.     register path *pp;
  437. {
  438.     register int i;
  439.     register path pa = Parent(*pp);
  440.  
  441.     i = ichild(*pp) + 1;
  442.     if (!pa || i > Nchildren(Tree(pa)))
  443.         return No;
  444.     if (!up(pp))
  445.         return No;
  446.     return downi(pp, i);
  447. }
  448.  
  449.  
  450. /*
  451.  * Highest level: small utilities.
  452.  *
  453.  * WARNING: Several of the following routines may change their argument
  454.  * even if they return No.
  455.  * HINT: Some of these routines are not used; they are included for
  456.  * completeness of the provided set of operators only.  If you have
  457.  * space problems (as, e.g., on a PDP-11), you can delete the superfluous
  458.  * ones (lint will tell you which they are).
  459.  */
  460.  
  461. Visible Procedure
  462. top(pp)
  463.     register path *pp;
  464. {
  465.     while (up(pp))
  466.         ;
  467. }
  468.  
  469.  
  470. Visible bool
  471. nextnode(pp)
  472.     register path *pp;
  473. {
  474.     while (!rite(pp)) {
  475.         if (!up(pp))
  476.             return No;
  477.     }
  478.     return Yes;
  479. }
  480.  
  481.  
  482. Visible Procedure
  483. firstleaf(pp)
  484.     register path *pp;
  485. {
  486.     while (down(pp))
  487.         ;
  488. }
  489.  
  490. #if NOT_USED
  491.  
  492. Visible bool
  493. nextleaf(pp)
  494.     register path *pp;
  495. {
  496.     if (!nextnode(pp))
  497.         return No;
  498.     firstleaf(pp);
  499.     return Yes;
  500. }
  501.  
  502. #endif NOT_USED
  503.  
  504. Visible bool
  505. prevnode(pp)
  506.     register path *pp;
  507. {
  508.     while (!left(pp)) {
  509.         if (!up(pp))
  510.             return No;
  511.     }
  512.     return Yes;
  513. }
  514.  
  515. Visible Procedure
  516. lastleaf(pp)
  517.     register path *pp;
  518. {
  519.     while (downrite(pp))
  520.             ;
  521. }
  522.  
  523. #ifdef NOT_USED
  524.  
  525. Visible bool
  526. prevleaf(pp)
  527.     register path *pp;
  528. {
  529.     if (!prevnode(pp))
  530.         return No;
  531.     lastleaf(pp);
  532.     return Yes;
  533. }
  534.  
  535.  
  536. Visible bool
  537. nextmarked(pp, x)
  538.     register path *pp;
  539.     register markbits x;
  540. {
  541.     do {
  542.         if (!nextnode(pp))
  543.             return No;
  544.     } while (!marked(*pp, x));
  545.     while (down(pp)) {
  546.         while (!marked(*pp, x)) {
  547.             if (!rite(pp)) {
  548.                 up(pp) || Abort();
  549.                 return Yes;
  550.             }
  551.         }
  552.     }
  553.     return Yes;
  554. }
  555.  
  556. #endif NOT_UED
  557.  
  558. Visible bool
  559. firstmarked(pp, x)
  560.     register path *pp;
  561.     register markbits x;
  562. {
  563.     while (!marked(*pp, x)) {
  564.         if (!up(pp))
  565.             return No;
  566.     }
  567.     while (down(pp)) {
  568.         while (Type(tree(*pp)) == Tex || !marked(*pp, x)) {
  569.             if (!rite(pp)) {
  570.                 up(pp) || Abort();
  571.                 return Yes;
  572.             }
  573.         }
  574.     }
  575.     return Yes;
  576. }
  577.  
  578.  
  579. Visible bool
  580. prevmarked(pp, x)
  581.     register path *pp;
  582.     register markbits x;
  583. {
  584.     do {
  585.         if (!prevnode(pp))
  586.             return No;
  587.     } while (!marked(*pp, x));
  588.     while (downrite(pp)) {
  589.         while (!marked(*pp, x)) {
  590.             if (!left(pp)) {
  591.                 up(pp) || Abort();
  592.                 return Yes;
  593.             }
  594.         }
  595.     }
  596.     return Yes;
  597. }
  598.  
  599.  
  600. /*
  601.  * Deliver the path length to the root.
  602.  */
  603.  
  604.  
  605. Visible Procedure
  606. pathlength(p)
  607.     register path p;
  608. {
  609.     register int n;
  610.  
  611.     for (n = 0; p; ++n)
  612.         p = parent(p);
  613.     return n;
  614. }
  615.  
  616.  
  617. /*
  618.  * Put a C string in a trimmed location (this name should change,
  619.  * the 'official' routine of this name has quite different parameters).
  620.  */
  621.  
  622.  
  623. Visible Procedure
  624. putintrim(pn, head, tail, str)
  625.     register value *pn;
  626.     register int head;
  627.     Register int tail;
  628.     Register string str;
  629. {
  630.     register value v = *pn; 
  631.     value w = head == 0 ? mk_text("") :
  632.         head == Length(v) ? copy(v) : trim(v, 0, Length(v) - head);
  633.  
  634.     Assert(head >= 0 && tail >= 0 && head + tail <= Length(v));
  635.     if (*str)
  636.         concato(&w, str);
  637.     if (tail > 0)
  638.         concato(&w, Str(v)+(Length(v) - tail));
  639.     release(v);
  640.     *pn = w;
  641. }
  642.  
  643.  
  644. /*
  645.  * Touch the node in focus.
  646.  */
  647.  
  648. Visible Procedure
  649. touchpath(pp)
  650.     register path *pp;
  651. {
  652.     nodeuniql(Loctree(pp));
  653. }
  654.